package cuiyt.datastructure.searchtree.restructure;

import cuiyt.datastructure.searchtree.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author cyt
 * @describe
 * @create 2020-12-20 12:08
 */
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> rootNode;

    public int height() {
        if (rootNode == null) {
            return 0;
        }

        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(rootNode);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) { // 意味着即将要访问下一层
                levelSize = queue.size();
                height++;
            }
        }

        return height;
    }

    public int height2() {
        return height(rootNode);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public boolean isComplete() {
        if (rootNode == null) {
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(rootNode);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else { // 后面遍历的节点都必须是叶子节点
                leaf = true;
            }
        }

        return true;
    }

    /**
     * 前驱节点
     *
     * @param node
     * @return
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        // 前驱节点在左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }

    /**
     * 后继节点
     *
     * @param node
     * @return
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }

        // 前驱节点在左子树当中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    public int size() {
        return size;
    }

    public void clear() {
        rootNode = null;
        size = 0;
    }

    @Override
    public Object root() {
        return rootNode;
    }

    @Override
    public Object left(Object node) {
        return ((Node) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node) node).right;
    }

    @Override
    public Object string(Object node) {
        Node node1 = (Node) node;
        String patentString = "null";
        if (node1.parent != null) {
            patentString = node1.parent.value.toString();
        }
        return node1.value;
    }

    public static abstract class Visitor<E> {
        boolean isStop;

        /**
         * 具体的打印方法
         *
         * @param e
         * @return
         */
        protected abstract boolean visitor(E e);
    }

    public boolean isEmpty() {
        return size == 0;
    }


    public void levelOrder(Visitor visitor) {
        System.out.println("\nlevelOrder - > ");
        levelOrderMethod(rootNode, visitor);
    }

    private void levelOrderMethod(Node node, Visitor visitor) {
        if (node == null || visitor == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node remove = queue.remove();
            if (visitor.visitor(remove.value)) {
                return;
            }
            if (remove.left != null) {
                queue.add(remove.left);
            }
            if (remove.right != null) {
                queue.add(remove.right);
            }
        }
    }

    public void postOrder(Visitor visitor) {
        System.out.println("\npostOrder - > ");
        if (visitor == null) {
            return;
        }
        postOrderMethod(rootNode, visitor);
    }

    private void postOrderMethod(Node node, Visitor visitor) {
        if (node == null) {
            return;
        }
        postOrderMethod(node.left, visitor);
        postOrderMethod(node.right, visitor);
        if (visitor.isStop) {
            return;
        }
        visitor.isStop = visitor.visitor(node.value);
    }

    public void inOrder() {
        System.out.println("\ninOrder - > ");
        inOrderMethod(rootNode);
    }

    private void inOrderMethod(Node node) {
        if (node != null) {
            inOrderMethod(node.left);
            System.out.println(node.value);
            inOrderMethod(node.right);
        }
    }

    public void preOrder() {
        System.out.println("\npreOrder - > ");
        preOrderMethod(rootNode);
    }

    private void preOrderMethod(Node node) {
        if (node != null) {
            System.out.println(node.value);
            preOrderMethod(node.left);
            preOrderMethod(node.right);
        }
    }

    protected Node<E> createNode(E element, Node<E> parent) {
        return new Node<>(element, parent);
    }

    /**
     * 内部维护的节点， 使用节点来组成一个树
     *
     * @param <E>
     */
    protected static class Node<E> {
        E value;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        Node(E element, Node<E> parent) {
            this.value = element;
            this.parent = parent;
        }
    }
}
